Abduction is a form of inference that seeks the best explanation for the given observation. Because it provides a reasoning process based on background knowledge, it is used in applications that need convincing explanations. In this study, we consider weighted abduction, which is one of the commonly used mathematical models for abduction. The main difficulty associated with applying weighted abduction to real problems is its computational complexity. A state-of-the-art method formulates weighted abduction as an integer linear programming (ILP) problem and solves it using efficient ILP solvers; however, it is still limited to solving problems that include at most 100 rules of background knowledge and observations.

Abduction is a form of inference that seeks the best explanation for the given observation. Because it provides a reasoning process based on background knowledge, it is used in applications that need convincing explanations. In this study, we consider weighted abduction, which is one of the commonly used mathematical models for abduction. The main difficulty associated with applying weighted abduction to real problems is its computational complexity. A state-of-the-art method formulates weighted abduction as an integer linear programming (ILP) problem and solves it using efficient ILP solvers; however, it is still limited to solving problems that include at most 100 rules of background knowledge and observations. In this study, we first formulate the weighted abduction problem as a Max-SAT problem whose hard clauses are mostly Horn clauses. Then, we propose to solve the problem using modern Max-SAT solvers. In our experiments, the proposed method solved the problems much faster than the state-of-the-art ILP-based weighted abduction.

Abduction is widely used in the task of plan recognition, since it can be viewed as the task of finding the best explanation for a set of observations. The major drawback of abduction is its computational complexity. The task of abductive reasoning quickly becomes intractable as the background knowledge is increased. Recent efforts in the field of computational linguistics have enriched computational resources for commonsense reasoning. The enriched knowledge base facilitates exploring practical plan recognition models in an open-domain. Therefore, it is essential to develop an efficient framework for such large-scale processing. In this paper, we propose an efficient implementation of Weighted abduction. Our framework transforms the problem of explanation finding in Weighted abduction into a linear programming problem. Our experiments showed that our approach efficiently solved problems of plan recognition and outperforms state-of-the-art tool for Weighted abduction.